package 代码随想2._2链表;

/**
 * @author XXX
 * @date 2024-01-14 13:20
 */

import java.util.Stack;

/**
 * https://leetcode.cn/problems/reverse-linked-list/description/
 * 双指针法
 */
public class _3反转链表 {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return  head;
        ListNode newhead = null;
        while (head!=null){
            ListNode p = head.next;
            head.next = newhead;
            newhead = head;
            head = p;
        }
        return newhead;
    }

    // 迭代方法：增加虚头结点，使用头插法实现链表翻转
    public static ListNode reverseList1(ListNode head) {
        // 创建虚头结点
        ListNode dumpyHead = new ListNode(-1);
        dumpyHead.next = null;
        // 遍历所有节点
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            // 头插法
            cur.next = dumpyHead.next;
            dumpyHead.next = cur;
            cur = temp;
        }
        return dumpyHead.next;
    }

    //用栈
    public ListNode reverseList2(ListNode head) {
        // 如果链表为空，则返回空
        if (head == null) return null;
        // 如果链表中只有只有一个元素，则直接返回
        if (head.next == null) return head;
        // 创建栈 每一个结点都入栈
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 创建一个虚拟头结点
        ListNode pHead = new ListNode(0);
        cur = pHead;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            cur.next = node;
            cur = cur.next;
        }
        // 最后一个元素的next要赋值为空
        cur.next = null;
        return pHead.next;
    }
}
